﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LemonAlgorithm.SkylineAlgorithm
{
    public class SkylinePacker
    {
        // 矩形类 - 修正构造函数
        public class Rectangle
        {
            public float X { get; set; }
            public float Y { get; set; }
            public float Width { get; set; }
            public float Height { get; set; }
            public string Id { get; set; }
            public bool CanRotate { get; set; } = true;

            // 两个参数的构造函数
            public Rectangle(float width, float height, string id = "")
            {
                Width = width;
                Height = height;
                Id = id;
            }

            // 四个参数的构造函数
            public Rectangle(float x, float y, float width, float height, string id = "")
            {
                X = x;
                Y = y;
                Width = width;
                Height = height;
                Id = id;
            }

            public float Area => Width * Height;

            public void Rotate()
            {
                if (CanRotate)
                {
                    float temp = Width;
                    Width = Height;
                    Height = temp;
                }
            }
        }

        // 天际线段
        public class SkylineSegment
        {
            public float X { get; set; }
            public float Y { get; set; }
            public float Width { get; set; }
            public bool IsAvailable { get; set; } = true;

            public SkylineSegment(float x, float y, float width)
            {
                X = x;
                Y = y;
                Width = width;
            }

            public float EndX => X + Width;
        }

        // 放置候选
        public class PlacementCandidate
        {
            public int SegmentIndex { get; set; }
            public float X { get; set; }
            public float Y { get; set; }
            public float Waste { get; set; }
            public bool Rotated { get; set; }

            public PlacementCandidate(int segmentIndex, float x, float y, float waste, bool rotated)
            {
                SegmentIndex = segmentIndex;
                X = x;
                Y = y;
                Waste = waste;
                Rotated = rotated;
            }
        }

        // 保护字段，子类可以访问
        protected List<SkylineSegment> skyline;
        protected float containerWidth;
        protected float containerHeight;
        protected float wallClearance;

        public SkylinePacker(float containerWidth, float containerHeight, float wallClearance = 0f)
        {
            this.containerWidth = containerWidth;
            this.containerHeight = containerHeight;
            this.wallClearance = wallClearance;
            InitializeSkyline();
        }

        private void InitializeSkyline()
        {
            skyline = new List<SkylineSegment>
        {
            new SkylineSegment(wallClearance, wallClearance, containerWidth - 2 * wallClearance)
        };
        }

        // 主打包方法
        public virtual List<Rectangle> Pack(List<Rectangle> rectangles, PackingStrategy strategy = PackingStrategy.BestFit)
        {
            var sortedRectangles = SortRectangles(rectangles, strategy);
            var placedRectangles = new List<Rectangle>();

            foreach (var rect in sortedRectangles)
            {
                var candidate = FindBestPlacement(rect);

                if (candidate != null)
                {
                    rect.X = candidate.X;
                    rect.Y = candidate.Y;
                    if (candidate.Rotated && rect.CanRotate)
                    {
                        rect.Rotate();
                    }

                    placedRectangles.Add(rect);
                    UpdateSkyline(candidate.SegmentIndex, rect);
                }
            }

            return placedRectangles;
        }

        // 寻找最佳放置位置
        protected virtual PlacementCandidate FindBestPlacement(Rectangle rect)
        {
            var candidates = new List<PlacementCandidate>();

            for (int i = 0; i < skyline.Count; i++)
            {
                var segment = skyline[i];
                if (!segment.IsAvailable) continue;

                // 尝试不旋转
                TryAddPlacementCandidate(candidates, i, rect, false);

                // 尝试旋转
                if (rect.CanRotate)
                {
                    TryAddPlacementCandidate(candidates, i, rect, true);
                }
            }

            return candidates.OrderBy(c => c.Waste).FirstOrDefault();
        }

        protected virtual void TryAddPlacementCandidate(List<PlacementCandidate> candidates, int segmentIndex,
                                                      Rectangle rect, bool rotate)
        {
            float width = rotate ? rect.Height : rect.Width;
            float height = rotate ? rect.Width : rect.Height;

            var segment = skyline[segmentIndex];

            // 检查宽度是否足够
            if (segment.Width < width) return;

            // 计算放置的Y坐标
            float placementY = segment.Y;

            // 检查高度是否超出容器
            if (placementY + height > containerHeight - wallClearance) return;

            // 检查X方向是否有足够连续空间
            if (!CheckHorizontalSpace(segment.X, segmentIndex, width)) return;

            // 计算浪费的空间
            float waste = CalculateWaste(segmentIndex, segment.X, width, placementY);

            candidates.Add(new PlacementCandidate(segmentIndex, segment.X, placementY, waste, rotate));
        }

        protected virtual bool CheckHorizontalSpace(float startX, int startSegmentIndex, float requiredWidth)
        {
            float currentX = startX;
            float remainingWidth = requiredWidth;

            for (int i = startSegmentIndex; i < skyline.Count && remainingWidth > 0; i++)
            {
                var segment = skyline[i];
                if (!segment.IsAvailable) return false;

                float availableWidth = Math.Min(segment.Width - (currentX - segment.X), segment.Width);
                availableWidth = Math.Min(availableWidth, remainingWidth);

                // 检查高度是否一致
                if (segment.Y != skyline[startSegmentIndex].Y) return false;

                remainingWidth -= availableWidth;
                currentX += availableWidth;
            }

            return remainingWidth <= 0;
        }

        protected virtual float CalculateWaste(int segmentIndex, float x, float width, float y)
        {
            float waste = 0f;
            float currentX = x;
            float remainingWidth = width;

            for (int i = segmentIndex; i < skyline.Count && remainingWidth > 0; i++)
            {
                var segment = skyline[i];
                float segmentUsedWidth = Math.Min(segment.Width - (currentX - segment.X), remainingWidth);

                waste += segmentUsedWidth * (y - segment.Y);

                remainingWidth -= segmentUsedWidth;
                currentX += segmentUsedWidth;
            }

            return waste;
        }

        private List<Rectangle> SortRectangles(List<Rectangle> rectangles, PackingStrategy strategy)
        {
            switch (strategy)
            {
                case PackingStrategy.HeightDecreasing:
                    return rectangles.OrderByDescending(r => r.Height).ToList();
                case PackingStrategy.WidthDecreasing:
                    return rectangles.OrderByDescending(r => r.Width).ToList();
                case PackingStrategy.AreaDecreasing:
                    return rectangles.OrderByDescending(r => r.Area).ToList();
                case PackingStrategy.PerimeterDecreasing:
                    return rectangles.OrderByDescending(r => r.Width + r.Height).ToList();
                default:
                    return rectangles.OrderByDescending(r => Math.Max(r.Width, r.Height)).ToList();
            }
        }

        protected virtual void UpdateSkyline(int segmentIndex, Rectangle placedRect)
        {
            float rectEndX = placedRect.X + placedRect.Width;
            float newSegmentY = placedRect.Y + placedRect.Height;
            List<SkylineSegment> newSegments = new List<SkylineSegment>();

            // 处理放置矩形左侧的天际线
            for (int i = 0; i < segmentIndex; i++)
            {
                newSegments.Add(skyline[i]);
            }

            // 处理当前放置区域
            var currentSegment = skyline[segmentIndex];

            // 左侧剩余部分
            if (placedRect.X > currentSegment.X)
            {
                float leftWidth = placedRect.X - currentSegment.X;
                newSegments.Add(new SkylineSegment(currentSegment.X, currentSegment.Y, leftWidth));
            }

            // 顶部新天际线段
            newSegments.Add(new SkylineSegment(placedRect.X, newSegmentY, placedRect.Width));

            // 右侧剩余部分
            if (rectEndX < currentSegment.EndX)
            {
                float rightWidth = currentSegment.EndX - rectEndX;
                newSegments.Add(new SkylineSegment(rectEndX, currentSegment.Y, rightWidth));
            }

            // 添加剩余的天际线段
            for (int i = segmentIndex + 1; i < skyline.Count; i++)
            {
                newSegments.Add(skyline[i]);
            }

            // 合并相邻的相同高度的天际线段
            skyline = MergeSkylineSegments(newSegments);
        }

        private List<SkylineSegment> MergeSkylineSegments(List<SkylineSegment> segments)
        {
            if (segments.Count == 0) return segments;

            var merged = new List<SkylineSegment>();
            var current = segments[0];

            for (int i = 1; i < segments.Count; i++)
            {
                var next = segments[i];

                if (Math.Abs(current.Y - next.Y) < float.Epsilon &&
                    Math.Abs(current.EndX - next.X) < float.Epsilon)
                {
                    current = new SkylineSegment(current.X, current.Y, current.Width + next.Width);
                }
                else
                {
                    merged.Add(current);
                    current = next;
                }
            }

            merged.Add(current);
            return merged;
        }
    }

    public enum PackingStrategy
    {
        BestFit,
        HeightDecreasing,
        WidthDecreasing,
        AreaDecreasing,
        PerimeterDecreasing
    }
}
